home *** CD-ROM | disk | FTP | other *** search
/ Shareware Overload Trio 2 / Shareware Overload Trio Volume 2 (Chestnut CD-ROM).ISO / dir33 / stac-ms.zip / MS-SUIT < prev   
Text File  |  1993-02-03  |  8KB  |  180 lines
  1.  BBS: CCCBBS          Conference: Modems          Imported:  2/03/1993
  2.   To: ALL                             Num: 1287       Date:  2/03/1993
  3. From: ROSS WILLIAMS                    Re: 0          Time:  6:07 am
  4. Subj: MS-DOS 6 patent suit: Cal      Prvt: N          Read: N
  5.  
  6. Dear Netters,
  7.  
  8. As many of you may know by now, Microsoft is being sued by Stac
  9. Electronics who claim infringement of a data compression software
  10. patent. The patent is US Patent #4,701,745, the "Waterworth" patent,
  11. and has a priority date of 6 March 1985. Its abstract and claims
  12. sections appear at the end of this posting.
  13.  
  14. MS-DOS 6, due to be released in the first half of 1993, is the target
  15. of the Stac suit. MS-DOS 6 contains transparent disk compression, a
  16. key component of which is the data compression algorithm under
  17. dispute.
  18.  
  19. It's not hard to work out WHY this patent lawsuit exists. By
  20. incorporating transparent disk compression into MS-DOS, Microsoft
  21. will, for the first time, be competing directly with third-party
  22. transparent disk compression products, and this is likely to
  23. precipitate a shake-out in the niche. This filtering down from third
  24. party products to the operating system is a natural progression in
  25. technological development, and should be applauded (encryption is
  26. probably next in line). However, it must be extremely threatening to
  27. companies such as Stac Electronics who live in this transitory niche.
  28.  
  29. The patent turns out to be rather significant in a number of ways. Not
  30. only is it a very early software patent (1985), but it actually seems
  31. to cover most of the content of a LATER patent --- the "Gibson and
  32. Graybill" patent #5,049,881 (registered in 1990) --- so recently
  33. fought over by Intersecting Concepts and AdStor. This makes the
  34. Waterworth patent the king pin of a small tree of patents.
  35.  
  36. Having myself re-invented and published in 1989-1991 an algorithm (my
  37. LZRW1 algorithm) very similar to that described in the Waterworth
  38. patent, I am completely convinced of the patent's triviality. In a
  39. nutshell, the patent covers the use of hashing to find matches in a
  40. sliding input window. This is a fundamental and obvious technique in
  41. data compression and it is ludicrous that it should be anywhere but in
  42. the public domain. In fact it is ludicrous that it should have ever
  43. even existed as a piece of intellectual property.
  44.  
  45. The fact that a company as large as Microsoft is defendent in this
  46. case means that the stakes are high. If Microsoft wins then the whole
  47. tree of patents will fall. If Microsoft loses then it is unlikely that
  48. the patent will be challenged again and, as a consequence, it will be
  49. massively strengthened. I believe that it is in the interests of all
  50. those involved with data compression (except of course you know who)
  51. to see that this patent is toppled.
  52.  
  53. Because of my close involvement with these kinds of algorithms, and my
  54. sympathy with their cause in this instance, Microsoft is employing me
  55. on a contract basis to assist with the case. Currently I am collecting
  56. prior art. If you know of any prior art, or have any idea of where it
  57. might be obtained, I would be most grateful if you could contact me at
  58. the email address below.
  59.  
  60. Thanks,
  61.  
  62. Ross Williams
  63. ross@spam.adelaide.edu.au
  64.  
  65.  
  66. --<Start of Patent Abstract and Claims>--
  67.  
  68. UNITED STATES PATENT [19]       [11] Patent Number 4,701,745
  69. Waterworth                      [45] Date of Patent: Oct 20, 1987
  70. ------------------------------------------------------------------
  71. [54] DATA COMPRESSION PATENT
  72.  
  73. [75] Inventor: John R. Waterworth,
  74.                Cheadle, England.
  75. [73] Assignee: Ferranti, plc, Cheshire, England
  76. [21] Appl. No.: 835,793
  77. [22] Filed: Mar.3, 1986
  78. [30] Foreign Application Priority Data
  79.      Mar.6, 1985 [GB] United Kingdom.....8505790
  80. [51] Int Cl.^4 .................H03M 7/30
  81. [52] U.S. Cl. ................340/347 DD; 364/900
  82. [58] Field of Search......... 340/347 DD; 235/310;
  83.                               358/260, 261; 364/900
  84. [56]        References Cited
  85.           U.S. PATENT DOCUMENTS
  86. 4,054,951 10/1977  Jackson.......364/900
  87. Primary Examiner ---- Charles D. Miller
  88. Attorney, Agent, or Firm --- Kerkam, Stowell, Kondracki & Clarke
  89.  
  90. [57] ABSTRACT
  91.  
  92. A data compression system includes an input store (1) for receiving
  93. and storing a plurality of bytes of data from an outside source. Data
  94. processing means for processing successive bytes of data from the
  95. input store includes circuit means (21-25) operable to check whether
  96. a sequence of bytes is identical with a sequence of bytes already
  97. processed, output means (27) operable to apply to a transfer medium
  98. (12) each byte of data not forming part of such an identical sequence,
  99. and an encoder (26) responsive to the identification of such a
  100. sequence to apply to the transfer means (12) an identification signal
  101. which identifies both the location in the input store of the previous
  102. occurrence of the sequence of bytes and the number of bytes in the
  103. sequence.
  104.  
  105.                 8 Claims, 7 Drawing Figures
  106.  
  107.  
  108. CLAIMS SECTION
  109. --------------
  110. I claim:
  111.  
  112. 1. A data compression system comprising an input store for receiving
  113. and storing a plurality of bytes of uncompressed data from an outside
  114. source, and data processing means for processing successive bytes of
  115. data from the input store;
  116.  
  117. the data processing means including circuit means operable to check
  118. whether a sequence of successive bytes to be processed identical with
  119. a sequence of bytes already processed, and including hash generating
  120. means responsive to the application of a preedetermined number of
  121. bytes in sequence to derive a hash code appropriate to those bytes, a
  122. temporary store in which the hash code may represent the address of a
  123. storage location, and a pointer counter operable to store in the
  124. temporary store at said address a pointer indicative of the position
  125. in the input store of one of the predetermined number of bytes;
  126.  
  127. output means operable to apply to a transfer medium each byte of data
  128. not forming part of such an identical sequence; and
  129.  
  130. encoding means responsive to the identification of such a sequence to
  131. apply to the transfer medium an identification signal which identifies
  132. both the location in the input store of the previous occurrence of the
  133. sequence of bytes and the number of bytes contained in the sequence.
  134.  
  135. 2. A system as claimed in claim 1 in which the circuit means also
  136. includes check means operable to check for identity between each of
  137. the said predetermined number of bytes in sequence and each of a
  138. similar sequence of bytes contained in the input store at a location
  139. defined by a pointer read out from a temporary store at said address
  140. and to check whether identity exists between suceeeding bytes in each
  141. sequence of bytes, and a byte counter operable to count the number of
  142. identical bytes in each sequence.
  143.  
  144. 3. A system as claimed in claim 2 in which the encoder is operable
  145. when such identity exists to encode the pointer read out from the
  146. temporary store and the output of the byte counter.
  147.  
  148. 4. A system as claimed in 1 which includes a plurality of input
  149. stores each of which contains part only of the data from the
  150. outside source.
  151.  
  152. 5. A data comprtession system as claimed in claim 1 which includes
  153. data receiving means operable to receive compressed data from the
  154. transfer medium, an output store operable to store any uncompressed
  155. byte of data received by the receiving means, and copying means
  156. responsive to an identification signal to apply to the ouput store
  157. the sequence of bytes already contained in said output store and
  158. identified by the said identification signal, the arrangement being
  159. such that the data contained in the output store is the exact
  160. reconstruction of that applied at some earlier time to the input
  161. store.
  162.  
  163. 6. A system as claimed in claim 5 in which the data receiving means
  164. includes a decoder means operable to separate uncompressed bytes of
  165. data from identification signals.
  166.  
  167. 7. A system as claimed in claim 1 in which the transfer
  168. medium comprises a communications channel between two spaced
  169. locations.
  170.  
  171. 8. A system as claimed in claim 1 in which the transfer medium
  172. comprises a data storage medium.
  173.  
  174.                               * * * * *
  175.  
  176. --<End of Patent Abstract and Claims>--
  177.  
  178.  
  179.  
  180.